class Solution
{
public:
    int atMostNGivenDigitSet(vector<string> &digits, int n)
    {
        vector<int> nonGreaterCount(10, 0); // nonGreaterCount[i]表示digits中小于等于i的个数
        unordered_set<int> existDigits;
        int digitId = 0;
        int digitTypeCount = digits.size();
        for (int i = 1; i <= 9; ++i)
        {
            if (digitId < digitTypeCount && i == stoi(digits[digitId]))
            {
                existDigits.insert(i);
                nonGreaterCount[i] = nonGreaterCount[i - 1] + 1;
                ++digitId;
            }
            else
            {
                nonGreaterCount[i] = nonGreaterCount[i - 1];
            }
        }
        int origin = n;

        // 计算与n相同位数的整数个数
        string nStr = to_string(n);
        int maxLenNumCount = nonGreaterCount[nStr[0] - '0'];
        bool allExist = existDigits.count(nStr[0] - '0');
        for (int i = 1; i < nStr.size(); ++i)
        {
            int highBit = nStr[i] - '0';
            if (allExist)
            {
                // n的前面所有位都出现在digits中，则前面所写数字的最大值与n的前面部分相等
                // 前面数字不取到最大值时，有maxLenNumCount - 1种情况，此时这一位可以写所有digits
                // 前面数字取到最大值时，只有1种情况，此时这一位只能写小于等于highBit的值
                maxLenNumCount = (maxLenNumCount - 1) * digitTypeCount + nonGreaterCount[highBit];
            }
            else
            {
                // n前面某些位不出现在digits中，则前面所写数字的最大值一定小于n的前面部分
                // 此后都可以写任何digits
                maxLenNumCount *= digitTypeCount;
            }
            allExist = allExist && existDigits.count(highBit);
            if (maxLenNumCount == 0)
            {
                break;
            }
        }

        // 计算位数小于n的整数个数
        int lowerBitCount = floor(log10(origin));
        int nonMaxLenNumCount = 0;
        int a = digitTypeCount;
        for (int i = 0; i < lowerBitCount; ++i)
        {
            nonMaxLenNumCount += a;
            a *= digitTypeCount;
        }

        return maxLenNumCount + nonMaxLenNumCount;
    }
};